package william.hash;

import java.util.*;

/**
 * @author ZhangShenao
 * @date 2024/3/7
 * @description <a href="https://leetcode.cn/problems/group-anagrams/description/">...</a>
 */
public class Leetcode49_字母异位词分组 {
    /**
     * 采用排序+Map实现
     * 所有的字母异位词,进行字符串排序后一定相等
     * 使用Map记录异位词分组 key为排好序的字符串 value为所有字母异位词分组
     * 最后遍历Map,返回结果
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        //边界条件校验
        if (strs == null || strs.length < 1) {
            return Collections.emptyList();
        }

        //使用Map记录异位词分组 key为排好序的字符串 value为所有字母异位词分组
        Map<String, List<String>> frequencies = new HashMap<>(strs.length);
        for (String s : strs) {
            //对字符串进行排序
            //所有的字母异位词,进行字符串排序后一定相等
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);

            frequencies.putIfAbsent(key, new ArrayList<>());
            frequencies.get(key).add(s);
        }

        //遍历Map,返回结果
        List<List<String>> result = new ArrayList<>();
        for (Map.Entry<String, List<String>> e : frequencies.entrySet()) {
            List<String> anagrams = new ArrayList<>(e.getValue());
            result.add(anagrams);
        }
        return result;

    }

}
